package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/10/7.
 * 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],
 * 其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
 */
public class MultiplyArr {

    /**
     * 思路
     * 不能用除法，我们可以根据规律创建一个矩阵，
     * 把B[]分成两部分，分为A[0]A[i-1]和A[i+1]A[n-1]，分别计算这个矩阵中的每行的两部分（就是叠乘），
     * 就可以通过一层循环计算出来，复杂度为O(n)
     * */
    public int[] multiply(int[] A) {
        int[] result = null;
        if (A == null || A.length == 0) {
            return result;
        }
        result = new int[A.length];
        int[] C = new int[A.length];
        C[0] = 1;
        int[] D = new int[A.length];
        D[A.length - 1] = 1;
        for (int i = 1; i < A.length; i++) {
            C[i] = C[i - 1] * A[i - 1];
            D[A.length - 1 - i] = D[A.length - 1 - (i - 1)] * A[A.length - 1 - (i - 1)];
        }
        for (int i = 0; i < A.length; i++) {
            result[i] = C[i] * D[i];
        }
        return result;
    }
}
